import java.util.BitSet;

/**
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * <p>
 * 输入：matrix = [['1','0','1','0','0'],['1','0','1','1','1'],['1','1','1','1','1'],['1','0','0','1','0']]
 * 输出：6
 * 解释：最大矩形如上图所示。
 * 示例 2：
 * <p>
 * 输入：matrix = []
 * 输出：0
 * 示例 3：
 * <p>
 * 输入：matrix = [['0']]
 * 输出：0
 * 示例 4：
 * <p>
 * 输入：matrix = [['1']]
 * 输出：1
 * 示例 5：
 * <p>
 * 输入：matrix = [['0','0']]
 * 输出：0
 *  
 * <p>
 * 提示：
 * <p>
 * rows == matrix.length
 * cols == matrix.length
 * 0 <= row, cols <= 200
 * matrix[i][j] 为 '0' 或 '1'
 */
class Solution {

    public static void main(String[] args) {
        char[][] all = new char[4][5];
        all[0] = new char[]{'1', '0', '1', '0', '0'};
        all[1] = new char[]{'1', '0', '1', '1', '1'};
        all[2] = new char[]{'1', '1', '1', '1', '1'};
        all[3] = new char[]{'1', '0', '0', '1', '0'};
       /* char[][] all = new char[2][2];
        all[0] = new char[]{'0', '1'};
        all[1] = new char[]{'0', '1'};*/
        System.out.println(maximalRectangle(all));
    }

    /**
     * @param matrix
     * @return
     */
    public static int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int area = 0;
        // 处理出当前的值前面存在多少个1
        int[][] msg = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '1') {
                    if (j > 0) {
                        msg[i][j] = msg[i][j - 1] + 1;
                    } else {
                        msg[i][j] = 1;
                    }
                } else {
                    msg[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (msg[i][j] > 0) {
                    area = Math.max(area, msg[i][j]);
                    // 开始处理，判断是否存在上一个且上一个不为0
                    int min = msg[i][j];
                    for (int k = 1; k <= i; k++) {
                        min = Math.min(min, msg[i - k][j]);
                        if (min > 0) {
                            area = Math.max(area, min * (k + 1));
                        } else {
                            break;
                        }
                    }
                }
            }
        }

        return area;
    }

    /**
     * 位图算法，性能不好
     *
     * @param matrix
     * @return
     */
    public static int maximalRectangle2(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int area = 0;
        int x = matrix[0].length, y = matrix.length;
        BitSet[][] bitSets = new BitSet[y][y];
        // 初始转换matrix为BitSet
        for (int i = 0; i < y; i++) {
            BitSet bitSet = new BitSet(x);
            for (int j = 0; j < x; j++) {
                if (matrix[i][j] == '1') {
                    bitSet.set(j, true);
                }
            }
            area = Math.max(area, score(bitSet, 1));
            bitSets[i][i] = bitSet;
        }
        // 遍历所有情况
        for (int len = 2; len <= y; len++) {
            for (int s = 0; s <= y - len; s++) {
                int split = s + len - 1;
                BitSet one = bitSets[s][split - 1];
                BitSet sum = (BitSet) one.clone();
                BitSet two = bitSets[split][split];
                sum.and(two);
                area = Math.max(area, score(sum, len));
                bitSets[s][split] = sum;
            }
        }
        return area;
    }

    /**
     * 计算分数
     */
    public static int score(BitSet bitSet, int len) {
        int max = 0, tmp = 0;
        for (int i = 0; i < bitSet.length(); i++) {
            if (bitSet.get(i)) {
                tmp++;
                max = Math.max(max, tmp);
            } else {
                tmp = 0;
            }
        }
        return max * len;
    }

}